#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const int N = 2e5 + 10;
#define INF 0x3f3f3f3f;
typedef long long int ll;
#define close(); std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
//----------------------------------------------------------------------------//
int n, k;
int a[N];
void solve()
{
	memset(a,0,sizeof a);
	cin >> n >> k;
	int k2 = k;

	string s;
	cin >> s;

	int much = 0;
	if (k % 2 == 1)//奇数,整体的变化会导致原本为0的偶数变化
	{
		for (int i = 0; i < n; i++)
		{
			if (k == 0) break;
			if (s[i] == '1' && k > 0)//对于这个位置操作数数为k-1为偶数则不变
			{
				//s[i] = '1'; k--;
				a[i]=1,k--;
			}
		}
		if(k!=0) a[n-1]+=k;//加等的原因是很可能最后一个数字也被操作了,但是还是多余了部分操作数量
	}
	else
	{
		for (int i = 0; i < n; i++)
		{
			if (k == 0) break;
			if (s[i] == '0' && k > 0)//偶数让1不变,让0改变,该0位置操作为k-1为奇数
			{
				//s[i] = '1'; k--;
				a[i]=1,k--;
			}
		}
		if(k!=0) a[n-1]+=k;  
	}
	for (int i = 0; i < n; i++)
	{
		// if ((k2 - (s[i] - '0')) % 2 == 0) cout << s[i];
		// else cout << (s[i] == '0' ? 1 : 0);

		if((k2-a[i])%2==0) cout<<s[i];//只要a中某位元素为1,那么一定是变化过的
		else cout << (s[i] == '0' ? 1 : 0);
	}
	cout<<'\n';
	for(int i=0;i<n;i++)cout<<a[i]<<" ";
    cout<<"\n";
	// if ((k2 - k-(s[n-1] - '0')) & 1) cout << (s[n-1] == '1' ? 0 : 1)<<'\n';
	// else cout << s[n-1]<<'\n';


	//for(int i=0;i<n;i++)


}

int main()
{
	close();
	int T; cin >> T;
	while (T--) solve();
	return 0;
}
//偶数不影响结果